﻿
#ifndef __HASH_TABLE__
#define __HASH_TABLE__

// 实现步骤：
// 1、实现哈希表
// 2、封装unordered_map和unordered_set的框架 解决KeyOfT
// 3、iterator
// 4、const_iterator
// 5、key不⽀持修改的问题
// 6、operator[]

// 【除法散列法（h(key) = key % M）】作为哈希函数，开放定址法中的【线性探测】处理插入数据时的冲突
namespace yyp
{
	// 泛型编程，数据类型设为T。T可以是单独的key，也可以是key-val类型的键值对
	template <class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			: _data(data)
			, _next(nullptr)
		{}
	};

	template <class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return static_cast<size_t>(key);
		}
	};

	// 模板的特化
	template <>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;

			for (const auto& e : s)
			{
				hash += e;
				hash *= 131;	// 溢出时自行回绕，关键是尽量不重复
			}

			return hash;
		}
	};

	// 前置声明
	template <class K, class T, class KeyofT, class Hash>
	class HashTable;

	template <class K, class T, class Ref, class Ptr, class KeyofT, class Hash>
	class HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyofT, Hash> HT;
		typedef HTIterator<K, T, Ref, Ptr, KeyofT, Hash> Self;

	public:
		HTIterator(Node* node, const HT* ht)	// const Node* node参数设计，权限放大。_node的类型是 Node*
			: _node(node)
			, _ht(ht)
		{}

		Ref& operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		// 前置++
		Self& operator++()
		{
			if (_node)
			{
				if (_node->_next)
				{
					// 当前桶还有数据，走到当前桶下一个节点
					_node = _node->_next;
				}
				else
				{
					// 当前桶走完了，找下一个不为空的桶
					size_t hashi = Hash()(KeyofT()(_node->_data)) % _ht->_table.size();
					
					++hashi;
					for (size_t n = _ht->_table.size(); hashi < n; ++hashi)
					{
						if (_ht->_table[hashi])
						{
							_node = _ht->_table[hashi];
							break;
						}
					}
					// 所有桶都走完了，end()使用的空标识_node是nullptr
					if (hashi == _ht->_table.size())
						_node = nullptr;
				}
			}

			return *this;
		}

		// 后置++
		Self operator++(int)
		{
			Self tmp(*this);// 创建一个当前迭代器的副本
			++(*this);		// 对当前迭代器进行前置自增操作

			return tmp;		// 返回副本，副本的值是自增前的值。使用默认拷贝构造的浅拷贝即可
		}

	private:
		Node* _node;
		const HT* _ht;
	};

	template <class K, class T, class KeyofT, class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;

		friend class HTIterator<K, T, T&, T*, KeyofT, Hash>;
		friend class HTIterator<K, T, const T&, const T*, KeyofT, Hash>;

	public:
		typedef HTIterator<K, T, T&, T*, KeyofT, Hash> Iterator;
		typedef HTIterator<K, T, const T&, const T*, KeyofT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (0 == _n)
				return End();

			for (size_t i = 0, n = _table.size(); i < n; ++i)
			{
				Node* cur = _table[i];
				if (cur)
					return Iterator(cur, this);
			}

			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (0 == _n)
				return End();

			for (size_t i = 0, n = _table.size(); i < n; ++i)
			{
				Node* cur = _table[i];
				if (cur)
					return ConstIterator(cur, this);
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

	private:
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			return pos == last ? *(last - 1) : *pos;
		}

	public:
		HashTable()
			: _table(__stl_next_prime(0))	// C++中指针类型默认用nullptr初始化。初始值设为11方便调试
			, _n(0)
		{}

		// 拷贝构造和赋值重载也需要，暂未实现

		pair<Iterator, bool> Insert(const T& data)
		{
			KeyofT kot;
			Iterator it = Find(kot(data));
			if (it != End())
				return {it, false};

			Hash hash;
			size_t hash0 = 0;

			// 负载因子 == 1时扩容
			if (_n >= _table.size())
			{
				// 结合链表的结构特点，直接移动旧表中的节点即可
				vector<Node*> newTable(__stl_next_prime(_table.size() + 1), nullptr);

				for (size_t i = 0; i < _table.size(); ++i)
				{
					for (Node* cur = _table[i], *next = nullptr; cur; cur = next)
					{
						next = cur->_next;

						// 旧表中结点，挪到新表中重新映射的位置
						hash0 = hash(kot(cur->_data)) % newTable.size();

						// 头插到新表
						cur->_next = newTable[hash0];
						newTable[hash0] = cur;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			Node* newnode = new Node(data);
			hash0 = hash(kot(data)) % _table.size();

			// 头插
			newnode->_next = _table[hash0];
			_table[hash0] = newnode;
			++_n;

			return {Iterator(newnode, this), true};
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _table.size();

			for (Node* cur = _table[hash0], *prev = nullptr, *next = nullptr; cur;)
			{
				next = cur->_next;

				// 直接使用匿名对象 KeyofT()
				if (key == KeyofT()(cur->_data))
				{
					if (nullptr == prev)
					{
						// 只有一个节点（头节点）
						_table[hash0] = nullptr;
					}
					else
					{
						// 2个及以上的节点
						prev->_next = next;
					}

					delete cur;
					--_n;

					return true;
				}

				prev = cur;
				cur = next;
			}

			return false;
		}

		Iterator Find(const K& key)
		{
			KeyofT kot;
			size_t hash0 = Hash()(key) % _table.size();

			for (Node* cur = _table[hash0]; cur;)
			{
				if (key == kot(cur->_data))
				{
					return Iterator(cur, this);
				}

				cur = cur->_next;
			}

			return End();
		}

		~HashTable()
		{
			for (auto e : _table)
			{
				for (Node* cur = e, *next = nullptr; cur; cur = next)
				{
					next = cur->_next;
					delete cur;
				}

				e = nullptr;
			}

			_n = 0;
		}

	private:
		vector<Node*> _table;	// 指针数组
		size_t _n;				// 表中存储的数据个数
	};
}

#endif